package offerv1;

public class Offer07 {

    //preorder用于定位根节点
    //inorder用于确定左右子树的个数
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return new TreeNode(-1);
        }

        int n = preorder.length;
        if (n != inorder.length) {
            return new TreeNode(-1);
        }

        return helper(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode helper(int[] preorder, int[] inorder, int pLeft, int pRight, int iLeft, int iRight) {
        if (pLeft > pRight) {
            return null;
        }

        int num = preorder[pLeft];
        TreeNode node = new TreeNode(num);

        //利用hash提升效率
        int iIndex = 0;
        while (inorder[iIndex] != num) {
            iIndex++;
        }
        int iLeftSize = iIndex - iLeft;//左子树个数

        node.left = helper(preorder, inorder, pLeft + 1, pLeft + iLeftSize, iLeft, iIndex - 1);
        node.right = helper(preorder, inorder, pLeft + iLeftSize + 1, pRight, iIndex + 1, iRight);
        return node;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
